package 每日一题;

import com.alibaba.fastjson.JSON;

import java.util.*;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-10-08
 **/

public class No187重复的DNA序列 {

    /**
     * 所有 DNA 都由一系列缩写为 'A'，'C'，'G' 和 'T' 的核苷酸组成，例如："ACGAATTCCG"。
     * 在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。
     * 编写一个函数来找出所有目标子串，目标子串的长度为 10，且在 DNA 字符串 s 中出现次数超过一次。
     *
     * 示例 1：
     * 输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
     * 输出：["AAAAACCCCC","CCCCCAAAAA"]
     * 示例 2：
     * 输入：s = "AAAAAAAAAAAAA"
     * 输出：["AAAAAAAAAA"]
     *  
     * 提示：
     * 0 <= s.length <= 105
     * s[i] 为 'A'、'C'、'G' 或 'T'
     */

    public List<String> findRepeatedDnaSequences(String s) {

        if (s.length() <= 10) {
            return new ArrayList<>();
        }

        Set<String> set = new HashSet<>();
        Set<String> resultSet = new HashSet<>();

        int left = 0;
        int right = 10;

        while (right <= s.length()) {
            String substring = s.substring(left, right);
            if (set.contains(substring)) {
                resultSet.add(substring);
            }
            set.add(substring);
            left++;
            right++;
        }

        return new ArrayList<>(resultSet);
    }

    public static void main(String[] args) {
        No187重复的DNA序列 n = new No187重复的DNA序列();
        List<String> result = n.findRepeatedDnaSequences("AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT");
        System.out.println(JSON.toJSONString(result));
    }

}
